﻿using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

namespace Trains
{
    public class Train
    {
        private const string NotFoundRail = "NO SUCH ROUTE";
        private readonly Dictionary<string, Station> AllStations = new Dictionary<string, Station>();

        public string GetAllAnswers(string testDataPath)
        {
            InitializeData(testDataPath);
            var allAnswers = new List<string>();
            string answer1 = AnswerDistance("ABC");
            allAnswers.Add(GenAnswer(1, answer1));
            string answer2 = AnswerDistance("AD");
            allAnswers.Add(GenAnswer(2, answer2));
            string answer3 = AnswerDistance("ADC");
            allAnswers.Add(GenAnswer(3, answer3));
            string answer4 = AnswerDistance("AEBCD");
            allAnswers.Add(GenAnswer(4, answer4));
            string answer5 = AnswerDistance("AED");
            allAnswers.Add(GenAnswer(5, answer5));
            string answer6 = AnswerCLOOPMaxThreeStations();
            allAnswers.Add(GenAnswer(6, answer6));
            string answer7 = AnswerAtoCExactlyFourStations();
            allAnswers.Add(GenAnswer(7, answer7));
            string answer8 = AnswerAtoCShortestDistance();
            allAnswers.Add(GenAnswer(8, answer8));
            string answer9 = AnswerBtoBShortestDistance();
            allAnswers.Add(GenAnswer(9, answer9));
            string answer10 = AnswerCtoCAllDistanceLessThan30();
            allAnswers.Add(GenAnswer(10,answer10));
            return GenerateOutPut(allAnswers);
            
        }

        private string GenerateOutPut(List<string> allAnswers)
        {
            StringBuilder sbuilder=new StringBuilder();
            foreach (var answer in allAnswers)
            {
                sbuilder.AppendLine(answer);
            }
            return sbuilder.ToString();
        }

        internal string AnswerAtoCExactlyFourStations()
        {
            int sum = 0;
            List<string> allRoutine = GetAllStationRoutines(4, "A", "C");
            foreach (string routine in allRoutine)
            {
                if (routine[4] == 'C') sum++;
            }
            return sum.ToString();
        }

        internal string AnswerCLOOPMaxThreeStations()
        {
            List<string> allRoutine = GetAllStationRoutines(3, "C", "C");
            var result = new List<string>();
            foreach (string routine in allRoutine)
            {
                int indexOfC = routine.IndexOf('C', 1);
                if (indexOfC == -1) continue;
                string purePath = routine.Substring(0, indexOfC + 1);
                if (result.Contains(purePath))
                    continue;
                result.Add(purePath);
            }
            return result.Count.ToString();
        }

        internal void InitializeData(string testDataPath)
        {
            var reader = new StreamReader(testDataPath);
            string data = reader.ReadToEnd();
            BuildUpTrainStationGraph(data);
        }

        internal List<string> GetAllStationRoutines(int stationNumberLimit, string from, string to)
        {
            int currentPassedStation = 0;

            var stationHistory = new List<string>();

            stationHistory.Add(from);
            do
            {
                var appendHistory = new List<string>();
                foreach (string stationHisString in stationHistory)
                {
                    string lastStation = stationHisString[stationHisString.Length - 1].ToString();
                    Station station = GetStation(lastStation);
                    Dictionary<string, Rail> allOutRails = station.OutRails;
                    foreach (var rail in allOutRails)
                    {
                        string newHistory = stationHisString + rail.Value.NameTo;
                        appendHistory.Add(newHistory);
                    }
                }
                stationHistory = appendHistory;
                currentPassedStation++;
            } while (currentPassedStation < stationNumberLimit);
            return stationHistory;
        }

        private string GenAnswer(int sequence, string answer)
        {
            return string.Format("Output #{0}: {1}", sequence, answer);
        }

        internal string AnswerDistance(string stationSequence)
        {
            int sum = 0;
            for (int index = 0; index < stationSequence.Length - 1; index++)
            {
                Station from = GetStation(stationSequence[index].ToString());
                Rail rail = from.GetRail(stationSequence.Substring(index, 2));
                if (rail == null)
                    return NotFoundRail;
                sum += rail.Distance;
            }
            return sum.ToString();
        }

        private Station GetStation(string name)
        {
            if (AllStations.Keys.Contains(name))
                return AllStations[name];
            throw new Exception(string.Format("Station {0} is not defined.", name));
        }

        private void BuildUpTrainStationGraph(string data)
        {
            string[] datapieces = data.Split(',');
            foreach (string record in datapieces)
            {
                string recordtrim = record.Trim().ToUpper();
                string fromStation = recordtrim[0].ToString();
                string toStation = recordtrim[1].ToString();
                string infoleft = recordtrim.Substring(2);
                int distance = Convert.ToInt32(infoleft);
                PutStationIfNotExist(fromStation);
                PutStationIfNotExist(toStation);
                PutRailIfNotExist(fromStation, toStation, distance);
            }
        }

        private void PutRailIfNotExist(string fromStation, string toStation, int distance)
        {
            Station fromInstance = AllStations[fromStation];
            string railKey = fromStation + toStation;
            if (fromInstance.OutRails.ContainsKey(railKey))
                return;
            var newRail = new Rail(fromStation, toStation, distance);
            fromInstance.OutRails.Add(railKey, newRail);
        }

        private void PutStationIfNotExist(string station)
        {
            if (AllStations.Keys.Contains(station))
                return;
            var newStation = new Station();
            newStation.Name = station;
            AllStations.Add(station, newStation);
        }

        internal string AnswerAtoCShortestDistance()
        {
            int distance = GetShortCutRoutines("A", "C");
            return distance.ToString();
        }

        internal string AnswerBtoBShortestDistance()
        {
            int distance = GetShortCutRoutines("B", "B");
            return distance.ToString();
        }

        internal int GetShortCutRoutines(string from, string to)
        {
            var possibleRoutine = new Dictionary<string, int>();
            int shortCutDistance = Int32.MaxValue;
            possibleRoutine.Add(from, 0);
            while (possibleRoutine.Count > 0)
            {
                var possibleRoutineSwitch = new Dictionary<string, int>();
                foreach (var routine in possibleRoutine)
                {
                    string key = routine.Key;
                    string startName = key[key.Length - 1].ToString();
                    Station startStation = GetStation(startName);
                    Dictionary<string, Rail> allRails = startStation.OutRails;
                    foreach (var rail in allRails)
                    {
                        string nextStation = rail.Key[1].ToString();
                        int currentDistance = routine.Value + rail.Value.Distance;
                        if (routine.Key.Substring(1).Contains(nextStation))//make compatiable with B to B
                            continue; //loop
                        if (currentDistance >= shortCutDistance)
                            continue;//already too long
                        if (nextStation == to) //hit the end
                        {
                            if (currentDistance < shortCutDistance)
                                shortCutDistance = currentDistance;
                        }
                        else
                        {
                            possibleRoutineSwitch.Add(key + nextStation, currentDistance);
                        }
                    }
                }
                possibleRoutine = possibleRoutineSwitch;
            }
            return shortCutDistance;
        }

        internal string AnswerCtoCAllDistanceLessThan30()
        {
            int routineCount=GetPossibleRoutineLessThan("C", "C", 30);
            return routineCount.ToString();
        }

        internal int GetPossibleRoutineLessThan(string from, string to, int lessthan)
        {
            var possibleRoutine = new Dictionary<string, int>();
            var succeedRoutine = new Dictionary<string, int>();
            possibleRoutine.Add(from, 0);
            while (possibleRoutine.Count > 0)
            {
                var possibleRoutineSwitch = new Dictionary<string, int>();
                foreach (var routine in possibleRoutine)
                {
                    string key = routine.Key;
                    string startName = key[key.Length - 1].ToString();
                    Station startStation = GetStation(startName);
                    Dictionary<string, Rail> allRails = startStation.OutRails;
                    foreach (var rail in allRails)
                    {
                        //allow loop only check distance less than
                        string nextStation = rail.Key[1].ToString();
                        int currentDistance = routine.Value + rail.Value.Distance;
                        if (currentDistance >= lessthan)
                            continue;//already too long
                        if (nextStation == to) //hit the end
                        {
                            succeedRoutine.Add(key + nextStation, currentDistance);
                        }
                        possibleRoutineSwitch.Add(key + nextStation, currentDistance);
                        
                    }
                }
                possibleRoutine = possibleRoutineSwitch;
            }
            return succeedRoutine.Count;
        }
    }

    internal class Station
    {
        public Dictionary<string, Rail> OutRails = new Dictionary<string, Rail>();
        public string Name { get; set; }

        internal Rail GetRail(string name)
        {
            if (OutRails.Keys.Contains(name))
                return OutRails[name];
            return null;
        }
    }

    internal class Rail
    {
        public int Distance;

        public Rail(string from, string to, int distance)
        {
            NameFrom = from;
            NameTo = to;
            Distance = distance;
        }

        public string NameFrom { get; set; }
        public string NameTo { get; set; }
    }
}